The present invention pertains to the field of embroidery stitching and, more specifically, to manipulating singularities while automatically generating embroidery designs.
The needle and thread were the early sewing tools needed for mending and repairing damaged clothing. It was then discovered that the needle could be used as an artistic tool to stitch patterns of thread that displayed colorful designs. This patterning of thread into designs has become known as the art of embroidery. Over time, embroidery designs have been displayed on various items ranging in size and complexity from simple handkerchiefs to shirts and quilts.
Just as the sewing machine has automated the task of sewing, various mechanisms have been used to automate the art of embroidery. For example, it has become known that a computer can be used to automatically generate embroidery designs. Typically an embroidery design is recreated from a pattern that is displayed on paper. However, when a computer is used to create an embroidery design, many factors must be considered in order to produce an accurate interpretation of the pattern. Factors such as color contrast, line thickness and general object recognition, which are easily identifiable by the human eye, are sometimes not easily interpreted by a computer.
Computer systems have been developed for generating embroidery designs. For example, U.S. Pat. No. 5,668,730 describes part of a computer aided design system that allows a pattern to be scanned into a computer. When patterns are scanned into the computer, the scanner creates a file which depicts the characteristics of the scanned image. Once the file is created, these systems require human manipulation of the image to identify and distinguish its certain characteristics. For example, the user provides the outline in the image. This method of generating embroidery designs is not fully automated, since human manipulation of the image is required to ensure its accuracy. As a result of the required human interaction, this method of generating designs is inefficient and cumbersome.
A particular embroidery pattern cannot ever conform to any particular characteristics. Each pattern contains unique characteristics such as size and color. Depending upon how complex the pattern is, the human interaction required to interpret the scanned image may be significant, which thereby hampers the efficiency of the system.
U.S. Pat. No. 5,740,056 describes a method and device for producing embroidery data that also uses embroidery data that has been scanned into a file. Once the file is read in, continuous line components in the file are extracted and these line components are processed to generate start and end points needed for stitching. This method is not as accurate since no smoothing of the image is performed before fine line components are extracted.
As the complexity of items that require embroidery increases, the need for better mechanisms for automatically generating embroidery designs from a pattern becomes more apparent. To the extent that a mechanism cannot efficiently and accurately interpret intricate scanned patterns into embroidery designs, the ability to automate embroidery stitching is impaired.
One aspect of this field relates to structural indexing, which is related to shape recognition and/or image understanding. In xe2x80x9cStructural Indexing: Efficient 2-D Object Recognitionxe2x80x9d by F. Stein and G. Medioni, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, the authors attempted to recognize complete complex shapes. These shapes were limited to those having a single external edge contour (i.e., no holes within the shape). Specifically, metrics were extracted from line-approximated representations of the single edge contour of the shapes. Then, those metrics were used to index the contours within a larger database of contour models.
The Stein and Medioni reference serves as a good introduction to the basic concepts of structural indexing, but differs substantially from the present invention. Some key differences from this prior art include the use of a structural index to identify specific types of singularities, rather than entire shapes and the use of new, more appropriate, extracted metrics for this problem.
Other work has been presented within the field of handwriting recognition. Specifically, the recovery of temporal stroke information and restoration of occluded boundaries from images of cursive handwriting has been the subject of many journal articles. However, these approaches are narrowly focused within the domain of handwriting recognition and do not utilize the structural indexing approach presented here.
The methods presented in the aforementioned parent patent application form a strong and comprehensive basis for automatically generating embroidery designs from scanned images. However, to more completely replace human expertise in the automation process and improve the quality of data generated, a system must encapsulate dynamic learning capabilities as its human counterpart would. Thus, one aspect of the present invention addresses this important issue. Specifically, the utilization of a structurally indexed singularity database, combined with a unique and intuitive user interface, allows the automation system to actually learn from its human counterparts. This is believed to be a non-existent capability of any such similar system. For purposes of the description herein, the terms xe2x80x9csingular regionxe2x80x9d and xe2x80x9csingularityxe2x80x9d are considered interchangeable with each other, as are the terms xe2x80x9cregular regionxe2x80x9d and xe2x80x9cregularityxe2x80x9d with each other.
In accordance with the present invention, a method and apparatus for manipulating singular regions for automatic embroidery data generation is provided. The preferred embodiment of the present invention includes a singularity processing mechanism that allows singular regions of thin, predominantly regular shapes to be processed robustly in an accurate and aesthetically pleasing manner for subsequent embroidery data generation.
The singularity processing mechanism (SPM) operates upon the data structures created within the embroidery data generating mechanism described in the parent patent application, Ser. No. 09/134,981. The SPM includes an evaluate singularity mechanism that closely resembles the original mechanism of the parent case.
The evaluate singularity mechanism is responsible for determining an initial ordered set of reasonable interpretations for a singular region, while accommodating constraints such as minimization of energy required for reconstruction of occluded boundaries. The first item in this ordered set is the interpretation that the system deems most preferable, the second item being the second most preferable etc. Thus, the first interpretation item (or default choice), in many cases, will closely correspond to the output of the mechanism of the parent case.
Additionally, the evaluate singularity mechanism will interact with records within the stored singularity interpretation data, which is structurally indexed, to determine whether any similar singularities were previously encountered and processed in a unique way (i.e., different from the default first interpretation item). If one or more record matches are found within the stored singularity interpretation data, the data from these records is merged into the generated ordered set of reasonable interpretations. This will most likely produce a new first interpretation item (or default choice) that is a result of the system learning from a previously encountered singular region processed by the SPM.
The output of the evaluate singularity mechanism is forwarded to the user adjustment mechanism within the SPM. The user adjustment mechanism displays the first interpretation item (or default choice) for the user to accept or adjust/edit. A user""s acceptance of the default choice is implied when no adjustments are performed.
Several types of adjustments are possible and may be performed by the user via novel and efficient graphical user interface (GUI) elements. The first GUI element operates by displaying a small icon or shaded area within or around the singular region being processed, which may be clicked upon by the user. This GUI element may be considered as a control surface for allowing the user to make automated intelligent adjustments to the interpretation of the singularity. When activated, this element will cause an alternative interpretation of the singularity to be displayed, these alternatives having been defined within the ordered set of reasonable interpretations created previously by the evaluate singularity mechanism. Multiple activations will apply additional alternatives from this set of reasonable interpretations.
Other GUI elements operate by allowing the user to modify or replace the occluded boundaries generated automatically by the system. Modifications may include alterations of starting and ending points for sections of occluded boundaries, as well as the introduction of additional vertices or curvature that alter the shape of an occluded boundary.
If execution of the user adjustment mechanism indicates that, in fact, the user made one or more adjustments, the SPM executes the singularity storage mechanism. Otherwise, the SPM completes its execution and returns control back to the embroidery data generating mechanism described heretofore.
If the singularity storage mechanism is executed (again, indicating that adjustments were made), a set of operations ensue that effectively store the composition and nature of the singularity and any specific modifications made to its interpretation, within a structurally indexed non-volatile data store. Thus, this mechanism facilitates a feedback process that allows the system to learn from the user, since this data store will be utilized by the evaluate singularity mechanism for subsequent invocations of the SPM.